package com.cg.leetcode;

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 100.相同的树
 *
 * @program: LeetCode->LeetCode_100
 * @author: cg
 * @create: 2022-04-21 19:43
 **/
public class LeetCode_100 {

    @Test
    public void test100() {
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);
        TreeNode q = new TreeNode(1);
        q.left = new TreeNode(2);
        q.right = new TreeNode(3);
        System.out.println(isSameTree(p, q));
    }

    /**
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     * <p>
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     * <p>
     * 示例 1：
     * 输入：p = [1,2,3], q = [1,2,3]
     * 输出：true
     * <p>
     * 示例 2：
     * 输入：p = [1,2], q = [1,null,2]
     * 输出：false
     * <p>
     * 示例 3：
     * 输入：p = [1,2,1], q = [1,1,2]
     * 输出：false
     *  
     * 提示：
     * 两棵树上的节点数目都在范围 [0, 100] 内
     * -10^4 <= Node.val <= 10^4
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 递归
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null || q.val != p.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /*public boolean isSameTree(TreeNode p, TreeNode q) {
        // 迭代，使用队列
        // 双端队列可以模拟两个栈实现，只是进的时候是从两边进，出的时候从两边出，其他的都一样
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) {
                continue;
            }
            if (right == null || left == null || left.val != right.val) {
                return false;
            }
            queue.offer(left.left);
            queue.offer(right.left);
            queue.offer(left.right);
            queue.offer(right.right);
        }
        return true;
    }*/

}
